package leetcode;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
 * 
 * 假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
 * 
 * 例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。
 * 
 * 与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
 * 
 * 现在给定3个参数 — start, end,
 * bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
 * 
 * 注意:
 * 
 * 起始基因序列默认是合法的，但是它并不一定会出现在基因库中。 所有的目标基因序列必须是合法的。 假定起始基因序列与目标基因序列是不一样的。
 * 
 * @author maodou38
 *
 */
public class Solution433_leetcode_BFS_twoway {
	// 广度优先算法 双向
	public int minMutation(String start, String end, String[] bank) {
		HashSet<String> set = new HashSet<>(Arrays.asList(bank));
		if (!set.contains(end)) {
			return -1;
		}
		char[] four = { 'A', 'C', 'G', 'T' };
		HashSet<String> positive = new HashSet<String>() {
			{
				add(start);
			}
		};
		HashSet<String> negative = new HashSet<String>() {
			{
				add(end);
			}
		};
		HashSet<String> tempNewSet = new HashSet<>();
		int step = 0;
		while (positive.size() > 0 && negative.size() > 0) {
			step++;
			// 每次判断正向是否比负向的元素更多。我们选择元素更小的那个继续更新。
			if (positive.size() > negative.size()) {
				HashSet<String> temp = new HashSet<>(positive);
				positive = negative;
				negative = temp;
			}

			// 遍历每个正向的元素。
			for (String item : positive) {
				char[] tempStringChars = item.toCharArray();
				for (int i = tempStringChars.length - 1; i >= 0; --i) {
					char oldChar = tempStringChars[i];
					for (int j = 0; j < 4; ++j) {
						tempStringChars[i] = four[j];
						String newString = new String(tempStringChars);
						if (negative.contains(newString)) {
							return step;
						} else if (set.contains(newString)) {
							set.remove(newString);
							tempNewSet.add(newString);
						}
					}
					tempStringChars[i] = oldChar;
				}
			}
			positive = new HashSet<>(tempNewSet);
			tempNewSet.clear();
		}
		return -1;
	}
}
